/*
	Copyright (c) 2012 by karmaleaving@qq.com. All rights RESERVED.
*/
/*
	This file defines a red-black-tree in the "class btree".
*/
#ifndef __VTREE_H_VERSION_SSTD__
#define __VTREE_H_VERSION_SSTD__

#include "memory.hpp"
#include "functional.hpp"
SSTL_BEGIN
// CLASS btree {
template<typename Type, typename Less = SSTD::less<Type>, typename Allocate = SSTD::allocator<Type>, bool Mult = false>
class btree
{
	// TYPE {
public:
	SSTD_NEST_TYPE_DEFINE(Type);
protected:
	struct _node_data_;
	struct _node_base_;
	typedef _node_data_ _node_type;
	typedef _node_type * _node_pointer;
	class _iterator_;
	typedef SSTD::_memory_helper_<value_type> _helper;
public:
	STD_ITERATOR_DEFINE(_iterator_);
	typedef typename Allocate::template rebind<_node_data_>::other allocator_type;
	typedef Less compare_type;
	typedef Less key_compare;
	typedef Less value_compare;
	typedef SSTD::pair<const_iterator, const_iterator> range_pair;
	// TYPE }
protected:
	typedef allocator_type _allocator;
	// DATA {
	_node_pointer _head;
	size_type _size;
	compare_type _compare;
	allocator_type _alloc;
	_node_pointer _begin() const
	{
		return _min_node(_head);
	}
	_node_pointer _end() const
	{
		return 0;
	}
	_node_pointer _rbegin() const
	{
		return _max_node(_head);
	}
	_node_pointer _rend() const
	{
		return 0;
	}
	// DATA }
public:
	// CONSTRUCT & COPY & SWAP {
	btree() : _head(0), _size(0)
	{
	}
	btree(btree const &o) : _head(0), _size(0)
	{
		this->_copy(o);
	}
	~btree()
	{
		_clear();
		_tidy();
	}
	void operator = (btree const &o)
	{
		if(&o == this) return;
		this->_clear();
		this->_copy(o);
	}
	void swap(btree &o)
	{
		SSTD::swap(_head, o._head);
		SSTD::swap(_size, o._size);
	}
	// CONSTRUCT & COPY & SWAP }
public: 
	// INSERT {
	const_iterator insert(const_iterator, const_reference value)
	{
		bool flag;
		return _make_iterator(_insert(value, flag));
	}
	SSTD::pair<const_iterator, bool> insert(const_reference value)
	{				
		bool flag;
		return SSTD::make_pair(_make_iterator(_insert(value, flag)), flag);
	}
	template<typename InIter>
	void insert(InIter first, InIter last)
	{
		size_type num = SSTD::distance(first, last);
		bool flag;
		while(num--)
		{
			_insert(*first, flag);
		}
	}
	const_iterator erase(const_iterator first, const_iterator last)
	{
		while(first != last && first._node)
		{
			first = erase(first);
		}
		return first;
	}
	size_type erase(const_reference key)
	{
		_node_pointer node = _find(key);
		if(node)
		{
			_erase(node);
			return size_type(1);
		}
		else return size_type(0);
	}
	const_iterator erase(const_iterator iter)
	{
		ASSERT_REPAIR(_valid_data(iter), return end());
		return _make_iterator(_erase(iter._node));
	}
	// INSERT }
	// VISIT {
	const_iterator find(const_reference key)
	{
		return _make_iterator(_find(key));
	}
	void clear()
	{
		this->_clear();
	}
	bool empty() const
	{
		return _size == 0;
	}
	size_type size() const
	{
		return _size;
	}
	allocator_type get_allocator() const
	{
		return _alloc;
	}
	size_type max_size() const
	{
		return _allocator::max_size();
	}
	key_compare key_comp() const
	{
		return _compare;
	}	
	value_compare value_comp() const
	{
		return _compare;
	}
	template<typename Value>
	size_type count(Value const &value) const
	{
		return _count(_head, value);
	}	
	const_iterator begin() const
	{
		return (const_iterator)_make_iterator(_begin());
	}
	const_iterator end() const
	{
		return (const_iterator)_make_iterator(_end());
	}	
	const_reverse_iterator rbegin() const
	{
		return (const_reverse_iterator)_make_iterator(_rbegin());
	}
	const_reverse_iterator rend() const
	{
		return (const_reverse_iterator)_make_iterator(_rend());
	}
	// VISIT }
protected:
	// FIND {
	range_pair equal_range(const_reference value)
	{
		return SSTD::make_pair(_lower_bound(value), _upper_bound(value));
	}
	template<typename Value>
	_node_pointer _lower_bound(Value  const & value)
	{
		_node_pointer cur = _head, bound = _end();
		while(cur)
		{
			if(_compare(_visit(cur), value))
			{	// cur < value.
				cur = cur->right;
			}
			else
			{	// cur >= value.
				bound = cur;
				cur = cur->left;
			}
		}
		return bound;
	}
	template<typename Value>
	_node_pointer _upper_bound(Value  const & value)
	{
		_node_pointer cur = _head, bound = _end();
		while(cur)
		{
			if(_compare(value, _visit(cur)))
			{	// value < cur.
				bound = cur;
				cur = cur->left;
			}
			else
			{
				cur = cur->right;
			}
		}
		return bound;
	}
	template<typename Value>
	_node_pointer _find(Value const &value)
	{
		_node_pointer cur = _lower_bound(value);
		if(_visit(cur) == value) return cur;
		else return _end();
	}
	template<typename Value>
	size_type _count(_node_pointer src, Value const &value) const
	{
		if(!src) return size_type(0);
		if(_visit(src) == value)
		{
			if(Mult) return _count(src->left, value) + _count(src->right, value) + 1;
			else return size_type(1);
		}
		else if(_compare(_visit(src), value))
			return _count(src->right, value);
		else
			return _count(src->left, value);
	}
	// FIND }
	// INSERT & ERASE {
	void _clear()
	{
		if(_head)
		{
			_clear(_head);
			_head = 0;
		}
	}
	void _copy(btree const &o)
	{
		_size = o._size;
		_head = _copy(o._head);
	}
	template<typename Value>
	_node_pointer _insert_force(Value const &value)
	{
		_node_pointer cur = _head, node = 0;
		while(cur)
		{
			if(!cur->is_red && _RED(cur->right) && _RED(cur->left))
			{
				cur->right->is_red = cur->left->is_red = false;
				cur->is_red = true;
				_check_on_red(cur);
			}
			if(_compare(_visit(cur), value))
			{
				if(cur->right) cur = cur->right;
				else { cur->right = node = _make_node(value); break; }
			}
			else 
			{
				if(cur->left) cur = cur->left;
				else { cur->left = node = _make_node(value); break; }
			}
		}
		if(cur)
		{
			node->parent = cur;
			node->is_red = true;
			_check_on_red(node);
		}
		else
		{
			_head = node = _make_node(value);
			node->is_red = false;
		}
		++_size;
		return node;
	}
	template<typename Value>
	_node_pointer _insert(Value const &value, bool & insert_flag)
	{
		_node_pointer cur = _head, node = 0;
		while(cur)
		{			
			if(!Mult && _visit(cur) == value) 
			{
				return insert_flag = false, cur; // found.
			}
			if(!cur->is_red && _RED(cur->right) && _RED(cur->left))
			{
				cur->right->is_red = cur->left->is_red = false;
				cur->is_red = true;
				_check_on_red(cur);
			}
			if(_compare(_visit(cur), value))
			{
				if(cur->right) cur = cur->right;
				else { cur->right = node = _make_node(value); break;	}
			}
			else 
			{
				if(cur->left) cur = cur->left;
				else { cur->left = node = _make_node(value); break; }
			}
		}
		if(cur)
		{
			node->parent = cur;
			node->is_red = true;
			_check_on_red(node);
		}
		else
		{
			_head = node = _make_node(value);
			node->is_red = false;
		}
		++_size;
		return insert_flag = true, node;
	}
	_node_pointer _erase(_node_pointer node)
	{
		if(node->left && node->right)
		{
			_node_pointer temp = _min_node(node->right); // temp has no left son.
			_cut(temp, temp->right);
			_replace(node, temp);
			_erase_node(node);
			--_size;
			return temp;
		}
		else
		{
			_node_pointer temp = _next(node);
			_node_pointer o = (node->left == 0 ? node->right : node->left);
			_cut(node, o);	
			_erase_node(node);
			--_size;
			return temp;
		}
	}
	// INSERT & ERASE }
	// OPERATE {
	void _go_red(_node_pointer grand, _node_pointer parent, _node_pointer node)
	{	// node and parent is red.
		bool high_flag = (grand->left == parent);
		bool low_flag = (parent->left == node);
		if(high_flag == low_flag)
		{
			if(high_flag) _up_left(grand, parent);
			else _up_right(grand, parent);
			parent->is_red = !parent->is_red;
			grand->is_red = !grand->is_red;
		}
		else
		{
			if(high_flag) _up_left_right(grand, parent, node);
			else _up_right_left(grand, parent, node);
			grand->is_red = !grand->is_red;
			node->is_red = !node->is_red;
		}
	}
	void _go_black(_node_pointer parent, _node_pointer node)
	{	// node and parent is black.
		if(parent->left == node)
		{
			if(parent->right->is_red)
			{
				parent->right->is_red = false;
				_up_right(parent, parent->right);
				node->parent->left->is_red = node->parent->right->is_red = true;
			}
			else
			{
				_check_to_red(parent);				
				parent->is_red = false;
				parent->left->is_red = parent->right->is_red = true;
			}
		}
		else
		{
			if(node->parent->left->is_red)
			{
				parent->left->is_red = false;
				_up_left(node->parent, node->parent->left);
				node->parent->right->is_red = node->parent->left->is_red = true;
			}
			else
			{
				_check_to_red(node->parent);				
				node->parent->is_red = false;
				node->parent->left->is_red = node->parent->right->is_red = true;
			}
		}
	}
	void _up_left(_node_pointer parent, _node_pointer node)
	{	// node is left of parent.
		// Link parent and node's right.
		parent->left = node->right;
		if(node->right) node->right->parent = parent;
		// Link grand and node.
		node->parent = parent->parent;
		if(parent->parent)
		{
			(parent->parent->left == parent ?
				parent->parent->left : parent->parent->right) = node;
		}
		else _head = node;
		// Link node and parent.
		node->right = parent;
		parent->parent = node;
	}
	void _up_right(_node_pointer parent, _node_pointer node)
	{	// node is right of parent.
		// Link parent and node's left.
		parent->right = node->left;
		if(node->left) node->left->parent = parent;
		// Link grand and node.
		node->parent = parent->parent;
		if(parent->parent)
		{
			(parent->parent->right == parent ?
				parent->parent->right : parent->parent->left) = node;
		}
		else _head = node;
		// Link node and parent.
		node->left = parent;
		parent->parent = node;
	}
	void _up_right_left(_node_pointer grand, _node_pointer parent, _node_pointer node)
	{	// parent is right of grand, node is left of parent.
		// Link parent and node's right.
		parent->left = node->right;
		if(node->right) node->right->parent = parent;
		// link grand and node's left.
		grand->right = node->left;
		if(node->left) node->left->parent = grand;
		// Link grand-grand and node.
		node->parent = grand->parent;
		if(grand->parent)
		{
			(grand->parent->left == grand ?
				grand->parent->left : grand->parent->right) = node;
		}
		else _head = node;
		// Link node and parent.
		node->right = parent;
		node->left = grand;
		parent->parent = node;
		grand->parent = node;
	}
	void _up_left_right(_node_pointer grand, _node_pointer parent, _node_pointer node)
	{	// parent is left of grand, node is right of parent.
		// Link parent and node's right.
		parent->right = node->left;
		if(node->left) node->left->parent = parent;
		// link grand and node's right.
		grand->left = node->right;
		if(node->right) node->right->parent = grand;
		// Link grand-grand and node.
		node->parent = grand->parent;
		if(grand->parent)
		{
			(grand->parent->right == grand ?
				grand->parent->right : grand->parent->left) = node;
		}
		else _head = node;
		// Link node and parent.
		node->left = parent;
		node->right = grand;
		parent->parent = node;
		grand->parent = node;
	}
	void _check_on_red(_node_pointer node)
	{	// node is red. adjust the tree valid.
		if(!node->parent)
		{	// so node is head.
			node->is_red = false;
		}
		else if(node->parent->is_red)
		{	// so grandparent is not nil.
			_go_red(node->parent->parent, node->parent, node);
		}
	}
	void _check_to_red(_node_pointer node)
	{	// node is black. make it red and adjust the tree valid.
		if(!node->parent) ;
		else if(node->parent->is_red)
		{	// brother is black.
			node->parent->left->is_red = node->parent->right->is_red = true;
			node->parent->is_red = false;
		}
		else
		{
			_go_black(node->parent, node);
		}
	}	
	void _cut(_node_pointer parent, _node_pointer node)
	{	// parent has only son node, or no son if node is nil.
		if(parent->is_red) ;
		else if(_RED(node)) node->is_red = false;
		else _check_to_red(parent);
		if(parent->parent)
		{
			(parent->parent->left == parent ?
				parent->parent->left : parent->parent->right) = node;
		}
		else _head = node;
		if(node) node->parent = parent->parent;
	}
	void _replace(_node_pointer old, _node_pointer node)
	{
		node->parent = old->parent;
		node->left = old->left;
		node->right = old->right;
		if(node->left) node->left->parent = node;
		if(node->right) node->right->parent = node;
		if(node->parent)
			(node->parent->left == node ?
			node->parent->left : node->parent->right) = node;
		else _head = node;
	}
	// OPERATE }
	// INNER VISIT {
	static bool _RED(_node_pointer node)
	{
		return (node && node->is_red);
	}
	static _node_pointer _min_node(_node_pointer node)
	{
		if(!node) return 0;
		while(node->left)
		{
			node = node->left;
		}
		return node;
	}
	static _node_pointer _max_node(_node_pointer node)
	{
		if(!node) return 0;
		while(node->right)
		{
			node = node->right;
		}
		return node;
	}
	static _node_pointer _before_parent(_node_pointer node)
	{
		if(!node->parent) return 0;
		else if(node == node->parent->right) return node->parent;
		else return _before_parent(node->parent);
	}
	static _node_pointer _after_parent(_node_pointer node)
	{
		if(!node->parent) return 0;
		else if(node == node->parent->left) return node->parent;
		else return _after_parent(node->parent);
	}
	_node_pointer _next(_node_pointer node) const
	{
		if(!node) return _min_node(_head);
		if(node->right) return _min_node(node->right);
		return _after_parent(node);
	}
	_node_pointer _prev(_node_pointer node) const
	{
		if(!node) return _max_node(_head);
		if(node->left) return _max_node(node->left);
		return _before_parent(node);
	}
	// INNER VISIT }
	// ALLOCATE {
	template<typename Key>
	_node_pointer _make_node(Key const &value)
	{
		_node_pointer node; _allocate(node);
		node->parent = node->left = node->right = 0;
		node->is_red = true;
		_assign(node, value_type(value));
		return node;
	}
	void _erase_node(_node_pointer node)
	{
		_destroy(node);
		_deallocate(node);
	}
	void _allocate(_node_pointer &node)
	{
		node = _allocator::allocate(1);
	}
	void _deallocate(_node_pointer in)
	{
		_allocator::deallocate(in, 1);
	}
	void _assign(_node_pointer in, const_reference value)
	{
		_helper::raw_fill(&_visit(in), value);
	}
	void _destroy(_node_pointer &in)
	{
		_helper::destroy(&_visit(in));
	}
	void _tidy()
	{
	}
	// ALLOCATE }
	// FAST FUNCTION {
	_iterator_ _make_iterator(_node_pointer node) const
	{
		return (_iterator_(node, (btree*)this));
	}
	bool _valid_iterator(_iterator_ const &iter) const
	{
		return iter._container == this;
	}
	bool _valid_data(_iterator_ const &iter) const
	{
		return iter._container == this && iter._node != 0;
	}
	static value_type &_visit(_node_data_ * node)
	{
		return node->_data;
	}
	// FAST FUNCTION }
	// INNER CLASS {
	struct _node_base_
	{
		_node_data_ * parent;
		_node_data_ * left;
		_node_data_ * right;
		bool is_red;
	};
	struct _node_data_ : public _node_base_
	{
		value_type _data;
	};
	class _iterator_ 
		: public SSTD::iterator<SSTD::input_iterator_tag, value_type> 
	{
		friend class btree;
	protected:
		btree *_container;
		_node_pointer _node;
		_iterator_(_node_pointer node, btree *tree)
			: _container(tree), _node(node)
		{
		}
	public:
		_iterator_() : _container(0), _node(0)
		{
		}
		_iterator_(_iterator_ const &o)
			: _container(o._container), _node(o._node)
		{
		}
		_iterator_ & operator = (_iterator_ const &o) 
		{
			_node = o._node;
			_container = o._container;
			return *this;
		}
		_iterator_ &operator ++()
		{			
			_node = _container->_next(_node);
			return *this;
		}
		_iterator_ &operator --()
		{
			_node = _container->_prev(_node);
			return *this;
		}
		_iterator_ operator ++(int)
		{
			_iterator_ temp = *this;
			_node = _container->_next(_node);
			return temp;
		}		
		_iterator_ operator --(int)
		{
			_iterator_ temp = *this;
			_node = _container->_prev(_node);
			return temp;
		}
		value_type &operator * ()
		{
			return _visit(_node);
		}
		value_type *operator -> ()
		{
			return &_visit(_node);
		}
		bool operator == (_iterator_ const &o) const
		{
			return _node == o._node;
		}
	};
	// INNER CLASS }
private:
	// PRIVATE {
	void _clear(_node_pointer node)
	{
		if(node)
		{
			_clear(node->left);
			_clear(node->right);
			_erase_node(node);
			--_size;
		}
	}
	_node_pointer _copy(_node_pointer src)
	{
		_node_pointer node = 0;
		if(src)
		{
			node = _make_node(_visit(src));
			node->left = _copy(src->left);
			node->right = _copy(src->right);
			if(node->left) node->left->parent = node;
			if(node->right) node->right->parent = node;
		}
		return node;
	}
	// PRIVATE }
};
// CLASS btree }
SSTL_END

#endif // __VTREE_H_VERSION_SSTD__
